import java.util.Arrays;

//力扣152. 乘积最大子数组
class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;

        // maxSoFar：记录以当前元素结尾的子数组能得到的最大乘积
        // 初始化为第一个元素，因为单个元素本身就是一个子数组
        int maxSoFar = nums[0];

        // minSoFar：记录以当前元素结尾的子数组能得到的最小乘积
        // （用于处理负数的情况，因为负数乘以负数可能变成正数）
        // 同样初始化为第一个元素
        int minSoFar = nums[0];

        // maxProduct：全局最大值，最终需要返回的结果
        // 初始化为第一个元素
        int maxProduct = nums[0];

        for (int i = 1; i < n; i++) {
            // 临时保存 maxSoFar，因为下一步会更新它，但 minSoFar 的计算需要旧的 maxSoFar
            int tempMax = maxSoFar;

            // 更新 maxSoFar：可能的情况有三种：
            // 1. 当前元素 nums[i] 自己作为一个新子数组（比如之前乘积是负数，nums[i] 是正数）
            // 2. 当前元素乘以之前的最大乘积（正数乘正数）
            // 3. 当前元素乘以之前的最小乘积（负数乘负数，负负得正）
            maxSoFar = Math.max(nums[i], Math.max(maxSoFar * nums[i], minSoFar * nums[i]));

            // 更新 minSoFar：可能的情况有三种：
            // 1. 当前元素 nums[i] 自己作为一个新子数组（比如之前乘积是正数，nums[i] 是负数）
            // 2. 当前元素乘以之前的最大乘积（正数乘负数，结果更小）
            // 3. 当前元素乘以之前的最小乘积（负数乘正数，结果更小）
            minSoFar = Math.min(nums[i], Math.min(tempMax * nums[i], minSoFar * nums[i]));

            // 更新全局最大值
            maxProduct = Math.max(maxProduct, maxSoFar);
        }

        return maxProduct;
    }
}


//力扣300. 最长递增子序列
class Solution2 {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);  // 每个元素本身至少是一个长度为 1 的子序列

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        //每个位置都有一个最长递增子序列,长度各部相同
        int maxLen = 0;
        for (int len : dp) {
            maxLen = Math.max(maxLen, len);
        }
        return maxLen;
    }
}